package com.zhugang.week05;

/**
 * @program algorithms
 * @description: nextGreatestLetter
 * @author: chanzhugang
 * @create: 2022/07/05 15:43
 */
public class NextGreatestLetter {

    public static void main(String[] args) {
        NextGreatestLetter nextGreatestLetter = new NextGreatestLetter();
        char[] letters = new char[]{'c', 'f', 'j' };
        char res = nextGreatestLetter.nextGreatestLetter(letters, 'a');
        System.out.println(res);
    }

    /**
     * 744 寻找比目标字母大的最小字母
     *
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        // 标准二分变形： 第一个大于给定值的元素
        int low = 0;
        int high = letters.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (letters[mid] > target) {
                // 向前探测
                if (mid == 0 || letters[mid - 1] <= target) {
                    // 真命中
                    return letters[mid];
                } else {
                    // 伪命中
                    high = mid - 1;
                }
            } else {
                // 目标值在右边
                low = mid + 1;
            }
        }
        // 特殊处理：目标字母比所有都大，返回第一个
        return letters[0];
    }
}